package edu.cmu.cs211.chess.unittested;

import edu.cmu.cs211.chess.board.Board;
import edu.cmu.cs211.chess.board.Move;
import edu.cmu.cs211.chess.search.AbstractSearcher;

import java.util.HashMap;
import java.util.List;

/**
 * An implementation of Alpha Beta search.
 * 
 * This is the class that will be unit tested by FrontDesk.
 */
public class TestedAlphaBetaFixedDepth<M extends Move<M>, B extends Board<M, B>> extends AbstractSearcher<M, B> {
	// previously searched boards
	private HashMap<Long, B> history= new HashMap<Long, B>();

	public M getBestMove(B board, int myTime, int opTime)
	{
		List<M> moves = board.generateMoves();
		M result = null;
		int alpha = -evaluator.infty();
		for (M m : moves) 
		{
			board.applyMove(m);
			// recursively call alphabeta
			int newAlpha = -AB(board, -evaluator.infty(), evaluator.infty(), maxDepth-1);
			board.undoMove();
			
			// update the alpha if we get a better score
			if (newAlpha > alpha) {
				alpha = newAlpha;
				result = m;
			}
		}
		// done searching, add this board to the hashtable
		history.put(board.signature(), board);
		return result;
	}

	private int AB(B board, int alpha, int beta, int depth)
	{
		// when we are at the bottom level, simply evaluate the board
		if (depth ==0)
			return evaluator.eval(board);
		
		/*
		 *  if this board has already been searched
		 *  return a small value as the score and keep searching other moves
		 */
		if(history.containsKey(board.signature()))
			return 0;
		
		List<M> moves = board.generateMoves();
		// no possible moves
		if (moves.isEmpty()) {
			if (board.inCheck()) 
				return -evaluator.mate();
			else 
				return -evaluator.stalemate();
		}
		
		// loop thru all possible moves and call alpha-beta on each move
		for (M m : moves) {
			board.applyMove(m);
			int newAlpha = -AB(board, -beta, -alpha, depth-1);
			board.undoMove();
			if (newAlpha > alpha) 
				alpha = newAlpha;
			// cutoff
			if (alpha >= beta) 
				return alpha;
		}
		return alpha;
	}

}